Codeforces Round #623 Div2 A~D题解

本场链接:Codeforces Round #623
A. Dead Pixel
题目大意:有一个aba\star b大小的电视机,坐标从00开始.上面有一个像素点坏了,问不包括这个坏掉的像素点的矩形最大的面积是多少.
数据范围:
1a,b1041 \leq a,b \leq 10^4
a+b>2a + b > 2

这题还是比较显然的,去掉这个坏掉的像素点之后,最大的矩形就四种情况,分别求一个最大值就行了.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,m,x,y;scanf("%d%d%d%d",&n,&m,&x,&y);
		int res = 0;
		res = max(res,max(n * y,n * (m - y - 1)));
		res = max(res,max(m * x,m * (n - x - 1)));
		printf("%d\n",res);
    }
    return 0;
}

B. Homecoming
原题大意:一个人一开始在11号位置,一条路上一共有nn个车站,用一个字符串ss来表示整条路上的车站分布情况.车站一共有两种,一种是A,花费为aa,另外一种是B,花费为bb.车站的行驶规则是这样的:假如有一段i ji~j全是A或全是B,那么就可以从这段起点一直走到这一段的末尾的下一个位置(下一个位置可以是不同的),并支付相应的花费.现在已知aabb两种票价以及整条路径上的路线安排情况,以及手上有多少钱.问至少要走几步,才能使之后一直到nn位置都可以只坐车到达.要求不能欠钱,也不必把钱花完.最终输出至少有几步即可.
数据范围:
1a,b,p1051 \leq a,b,p \leq 10^5
2s1052 \leq |s| \leq 10^5

这题的题面有点长,不过理解了之后思路还是比较明确的,只要从后往前模拟就可以了.注意模拟的退出点是:手上钱不够购买一段连续区间的车票钱,或者是已经到头了.以及要记录一个当前这一段相同区间的左端点的答案,如果退出循环之后,手上的钱是足够购买这一段区间的票钱的,那么说明应该选择这一段的右端点,如果不够,应该选这一段的左端点.细节问题稍微有点说不清楚,建议自行模拟一下这个题的过程.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
char s[N];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int a,b,p;cin >> a >> b >> p;
		cin >> s + 1;
		int n = strlen(s + 1);
		int r = n - 1;
		int l = r,res = 0;
		while(l >= 0)
		{
			while(l >= 0 && s[l] == s[r])	--l;
			res = l + 1;
			if(l == 0)	break;
			if(s[r] == 'A')
			{
				if(p >= a)	p -= a;
				else break;
			}
			else if(s[r] == 'B')
			{
				if(p >= b)	p -= b;
				else break;
			}
				
			r = l;
		}
		if(p < ((s[r] == 'A') ? a : b))	cout << r + 1 << endl;
		else cout << res << endl;
	}
    return 0;
}

C. Restoring Permutation
题目大意:给定一个长度为nn的序列bb,找到一个字典序最小的排列aa,长度为2n2n,并满足bi=min(a2i,a2i1)b_i = min(a_{2i},a_{2i-1}),若不存在这样的排列cc,则输出1-1,否则输出cc
注意cc是一个排列,不是单纯的序列
数据范围:
1n1001 \leq n \leq 100

这题的数据范围一看这么小,肯定可以乱搞搞就过去了.
思考一下这个题具体是在问什么:找到一个排列cc,要使这个排列满足一个性质,如果有多个,就得是最小的.

显然,对于一个数字排列来说,只要数字越小字典序也就越小,首先肯定是能选小的就选小的.其次很容易想到这个题应该是一步一步,从后往前依次把bb里的元素放进去,再按bb的大小构造的,每次要往cc里造两个元素放进去,每两个都要满足之前的性质.不难想到说放完了一个bb里的元素之后,插入一个还没有用过的比当前元素要大的数接着放进去.因为要取最小值,,如果后一个bb里的元素被影响了(后面的这个数更大,导致之前插入给之前那个元素补更大的值在这里变成了一个较小值),说明无解.因为如果一个更大的数放在这里,这个较小的数之后不管怎样放,必然会产生矛盾,而且cc作为一个排列不能是缺少一些数的,所以无解.
要用没有用过的数的原因是最后的cc得是一个排列.最后如果还有没有用完的数,就把剩余的还没加进cc的数从小到大依次放进去就好了.
至于这个查找的过程,可以直接循环遍历一下,最多也就200200个数,随便写写就完事了.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		set<int> st;
		int n;scanf("%d",&n);
		vector<int> b(n + 17,0);
		if(n == 1)
		{
			scanf("%d",&b[0]);
			if(b[0] != 1)	puts("-1");
			else puts("1 2");
			continue;
		}
		for(int i = 1;i <= n;++i)	scanf("%d",&b[i]);
		for(int i = 1;i <= 2 * n;++i)	st.insert(i);
		for(int i = 1;i <= n;++i)	st.erase(b[i]);
		vector<int> a;a.push_back(0x3f3f3f3f);
		a.push_back(b[1]);
		for(int i = b[1];i <= 2 * n;++i)	
			if(st.count(i))
			{
				a.push_back(i);
				st.erase(i);
				break;
			}
		for(int i = 2;i <= n;++i)
		{
			a.push_back(b[i]);
			for(int j = b[i] + 1;j <= 2 * n;++j)
				if(st.count(j))
				{
					st.erase(j);
					a.push_back(j);
					break;
				}
		}
		for(int i = 1;i <= 2 * n;++i)
		{
			if(st.count(i))
				a.push_back(i);
		}
		//check
		int ok = 1;
		// for(auto& v : a)	cout << v << " ";cout << endl;
		for(int i = 1;i <= n;++i)
		{
			if(b[i] != min(a[2 * i],a[2 * i - 1]))
			{
				ok = 0;
				break;
			}
		}
		if(!ok)	puts("-1");
		else
		{
			for(int i = 1;i <= 2 * n;++i)
				printf("%d ",a[i]);
			puts("");
		}
    }
    return 0;
}

D. Recommendations
题目大意:有nn个元素,每个元素有两种属性,一是aia_i,另外一个是tit_i,表示如果要让aia_i加一,需要tit_i的代价.现要使所有的aia_i都不同,问最少需要多少代价.

数据范围:
1n21051 \leq n \leq 2\star 10^5
intint

这个题的关键在于,a_是动态变化的,如果我把一个aia_i加一,那么其他的aia_i的数量可能因此增加.这是一个动态的数量变化,与动态的变化的结构有很多,在这里比较容易依靠直觉想到的是堆或者用并查集维护.两种方法都可以做,这里讲一下并查集怎么做.
首先要知道并查集到底在维护什么,我们可以发现,如果对于某一个值来说,他增加了一次,那么之后所有其他值就不能采用他这个值了,就应该是这个值+1+1.所以可以维护每一个值xx最终需要是多少.对于第一个遇到的,就是xx,之后把xx的祖先连接到x+1x+1.动态的维护xx最终要是多少即可.
简略说一下整个算法流程:首先贪心的按tit_i倒序排列,因为较早出来的值其aia_i修改的次数也越少,这样可以贪心的使整个代价较小.其次遍历每一个元素,查他的祖先,即最终需要是多少,计算一个差值,求出这个差值和tit_i的乘积,得到应该需要增加几次,以及要多少的代价,并累加到答案里.
最后还有一个问题,因为aia_i的值高达10910^9,因此这里可以采用mapmap来做并查集,可以避免值域的问题(也就是避免写离散化,而且离散化貌似也不能处理增加的处理).
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2e5+7;
map<int,int> fa;
struct Node
{
	int a,b;
	const bool operator<(const Node& v) const
	{
		if(b != v.b)	return b > v.b;
		return a < v.a;
	}
}a[N];
int find(int x)
{
	if(fa[x] == 0)	return x;
	return fa[x] = find(fa[x]);
}
signed main()
{
	int n;scanf("%lld",&n);
	for(int i = 1;i <= n;++i)	scanf("%lld",&a[i].a);
	for(int i = 1;i <= n;++i)	scanf("%lld",&a[i].b);
	sort(a + 1,a + n + 1);
	ll res = 0;
	for(int i = 1;i <= n;++i)
	{
		int x = find(a[i].a);
		res += (x - a[i].a) * a[i].b;
		int nxt = find(x + 1);
		fa[x] = nxt;
	}
	printf("%lld",res);
    return 0;
}